package cn.com.leetcode.greedy;

import java.util.Arrays;

/**
 * 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
 * <p>
 * 以这种方式修改数组后，返回数组可能的最大和。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：A = [4,2,3], K = 1
 * 输出：5
 * 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
 * 示例 2：
 * <p>
 * 输入：A = [3,-1,0,2], K = 3
 * 输出：6
 * 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
 * 示例 3：
 * <p>
 * 输入：A = [2,-3,-1,5,-4], K = 2
 * 输出：13
 * 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo1005 {

    public static void main(String[] args) {
        Demo1005 demo1005 = new Demo1005();
        int[] A = {3, -1, 0, 2};
        int K = 3;
        int maxSum = demo1005.largestSumAfterKNegations(A, K);
        System.out.println(maxSum);
    }

    public int largestSumAfterKNegations(int[] A, int K) {
        int minPositiveNumber = Integer.MAX_VALUE;//最小的正整数
        int length = A.length;
        int index = 0;//指向第一个非负整数的位置，用于和下一个负数进行交换
        for (int i = 0; i < length; i++) {
            int num = A[i];
            //挑选出最小的正整数
            if (num >= 0 && num < minPositiveNumber) {
                minPositiveNumber = num;
            }
            //将负数交换到数组的前面
            if (A[i] < 0) {
                swap(A, i, index);
                index++;
            }
        }

        int minIndex = 0;
        int minNum = A[minIndex];
        //将最小的负数变为正数，并跟最后一个负数交换位置
        for (; index > 0 && K > 0; K--, index--) {
            for (int i = 1; i < index; i++) {
                if (minNum > A[i]) {
                    minNum = A[i];
                    minIndex = i;
                }
            }
            A[minIndex] = -A[minIndex];
            if (A[minIndex] < minPositiveNumber) {
                minPositiveNumber = A[minIndex];
            }
            swap(A, minIndex, index - 1);
            minIndex = 0;
            minNum = A[minIndex];
        }
        //求所有数据的和
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += A[i];
        }

        //如果 k != 0 则用和 减去两倍的 最小正整数
        return K % 2 == 1 ? sum - 2 * minPositiveNumber : sum;
    }

    private void swap(int[] A, int i, int index) {
        int t = A[i];
        A[i] = A[index];
        A[index] = t;
    }
}
